/*
 * @Author: 生俊甫 1758142861@qq.com
 * @Date: 2024-10-24 13:36:06
 * @LastEditors: 生俊甫 1758142861@qq.com
 * @LastEditTime: 2024-10-24 17:31:31
 * @FilePath: /sjf/2024-project/2024_centos/test_to_c/408_str/2020.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <iostream>
#include <string>
#include <limits.h>
#include <cmath>

/**
 * 2020年408真题的41题代码
 * 采用的是暴力算法，时间复杂度是O(N^3), 空间复杂度O(1)
 */

//暴力方法 O(N^3) C++
int find_min_path(std::string& s1, std::string& s2, std::string& s3)
{
    int min = INT_MAX;
    int a,b,c;
    for(int i = 0; i < s1.size(); i++)
    {
        for(int j = 0; j < s2.size(); j++)
        {
            for(int k = 0; k < s3.size(); k++)
            {
                int next_min =  std::abs(s1[i]-s2[j]) + std::abs(s2[j]-s3[k]) + std::abs(s3[k]-s1[i]);
                if(next_min < min)
                {
                    min = next_min;
                    a = s1[i];
                    b = s2[j];
                    c = s3[k];
                }
            }
        }
    }
    printf("{%d,%d,%d}\n",a,b,c);
    return min;
}

int main()
{
    std::string s1 = {-1,0,9};
    std::string s2 = {-25,-10,10,11};
    std::string s3 = {2,9,17,30,41};
    std::cout << find_min_path(s1,s2,s3) << std::endl;
    return 0;
}